package com.xiaoyu.arrays;

import java.util.Arrays;
import java.util.HashSet;

/**
 * @program: DS_and_A
 * @description: 删除数组重复项  LeetCode26
 *  给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
 * 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
 *
 * @author: YuWenYi
 * @create: 2021-04-22 09:26
 **/
public class RemoveDuplicates {
    /*
       本想利用set快速去重,但是不符合这题的题意
       HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        System.out.println(set);
    * */

    //返回新数组的长度length
    /*
    * 使用快慢双指针去解这道题!
    *
    * 坑点:这题并不是要真正的去删除数组中的元素,而是把不重复的元素放到最前面去,然后返回指定长度的数组
    *
    * slow指针:从0开始,用于保存的数字的连续下标
    * fast指针:用于遍历整个数组
    *
    * 如果,nums[slow] == nums[fast],那么代表此时是相同的值,那么只需要将快指针+1,遍历下一个元素
    *
    * 如果,nums[slow] != nums[fast],那么代表此时找到了一个新的值,
    * 此时才将慢指针+1,并把新值赋给慢指针的位置,并快指针+1,遍历下一个元素
    *
    * */
    public static int removeDuplicates(int[] nums) {
        // 使用快慢双指针
        int slow = 0,fast = 1;

        while (fast < nums.length){
      /*      if(nums[slow] == nums[fast]){
                fast++;
            }else {
                slow++;
                nums[slow] = nums[fast];
                fast++;
            }*/
            if (nums[slow] != nums[fast]) {
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
        }
        return slow+1;  //下标是5,所以长度需要+1
    }

    public static void main(String[] args) {
        int[] nums = new int[]{0,0,1,1,1,2,2,3,3,4,5};
        int len = removeDuplicates(nums);
        for (int i = 0; i < len; i++) {
            System.out.println(nums[i]);
        }
    }
}


